import java.net.HttpURLConnection;
import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mac
 * Date: 2022-11-03
 * Time: 18:49
 */
class MyHashMap {

    int[] map = new int[1000001];
    public MyHashMap() {
        Arrays.fill(map, -1);
    }

    public void put(int key, int value) {
        map[key] = value;
    }

    public int get(int key) {
        return map[key];
    }

    public void remove(int key) {
        map[key] = -1;
    }
}
//705.设计哈希集合 - 人才
class MyHashSet {

    /** Initialize your data structure here. */
    boolean[] map = new boolean[1000005];
    public MyHashSet() {

    }

    public void add(int key) {
        map[key] = true;
    }

    public void remove(int key) {
        map[key] = false;
    }

    /** Returns true if this set contains the specified element */
    public boolean contains(int key) {
        return map[key] == true;
    }
}
class ListNode{
    int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
}
public class Day13 {
    //203.移除链表元素
    public ListNode removeElements(ListNode head, int val) {
        if (head == null){
            return null;
        }
        ListNode cur = head;
        ListNode newHead = null;
        ListNode preCur = null;
        while (cur != null){
            if (cur.val != val){
                if (newHead == null){
                    newHead = preCur = cur;
                }else{
                    preCur.next = cur;
                    preCur = cur;
                }
            }
            cur = cur.next;
        }
        if (preCur != null){
            preCur.next = null;
        }
        return newHead;
    }
    //21.合并两个有序链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null){
            return list2;
        }
        if (list2 == null){
            return list1;
        }
        ListNode newHead = new ListNode(-1);
        ListNode cur = newHead;
        ListNode cur1 = list1;
        ListNode cur2 = list2;
        while (cur1 != null && cur2 != null){
            if (cur1.val < cur2.val){
                cur.next = cur1;
                cur1 = cur1.next;
            }else{
                cur.next = cur2;
                cur2 = cur2.next;
            }
            cur = cur.next;
        }
        if (cur1 != null){
            cur.next = cur1;
        }else{
            cur.next = cur2;
        }
        return newHead.next;
    }
    //83.删除排序链表中重复元素
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null){
            return null;
        }
        ListNode newHead = head;
        ListNode str = null;
        ListNode cur = head;
        while (cur != null){
            str = cur;
            while (cur.next != null && cur.val == cur.next.val){
                cur = cur.next;
            }
            cur = cur.next;
            str.next = cur;
        }
        return newHead;
    }
    //141.环形链表
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null){
            return false;
        }
        ListNode fast = head.next.next;
        ListNode slow = head;
        while (fast != null && fast.next != null && fast != slow){
            fast = fast.next.next;
            slow = slow.next;
        }
        if (fast == slow) {
            return true;
        }
        return false;
    }
    //160.相交链表 - 标记
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        if (headA == null || headB == null){
            return null;
        }
        ListNode last = headB;
        while (last.next != null){
            last = last.next;
        }
        last.next = headB;

        ListNode fast = headA;
        ListNode slow = headA;

        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                fast = headA;
                while (fast != slow){
                    fast = fast.next;
                    slow = slow.next;
                }
                last.next = null;
                return fast;
            }
        }
        last.next = null;
        return null;
    }

    //相交链表 - 网抑云
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null && headB == null) {
            return null;
        }
        ListNode curA = headA;
        ListNode curB = headB;
        while (curA != curB) {
            curA = curA == null ? headB : curA.next;
            curB = curB == null ? headA : curB.next;
        }
        return curA;
    }

    //706.设计哈希映射

    //测试用例
    public ListNode testFunction(int[] array){
        ListNode head = new ListNode(array[0]);
        ListNode cur = head;
        for (int i = 1; i < array.length; i++) {
            ListNode newNode = new ListNode(array[i]);
            cur.next = newNode;
            cur = newNode;
        }
        return head;
    }
}
